#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    int rob(vector<int> &nums)
    {
        if (nums.size() == 1)
        {
            return nums[0];
        }
        vector<vector<int>> dp(nums.size() + 1, vector<int>(nums.size() + 1, 0));
        dp[0][1] = nums[0]; // 第一家偷
        for (int i = 2; i < nums.size(); ++i)
        {
            dp[0][i] = max(dp[0][i - 1], dp[0][i - 2] + nums[i - 1]);
        }

        for (int i = 2; i <= nums.size(); ++i)
        {
            dp[1][i] = max(dp[1][i - 1], dp[1][i - 2] + nums[i - 1]);
        }
        return max(dp[0][nums.size() - 1], dp[1][nums.size()]);
    }
};